<?php

//排序
class SortTest {

    private $times = 0;

    //冒泡
    function sort_bubble($arr) {
        $n = count($arr);
        if ($n <= 1) {
            return $arr;
        }
        $this->times = 0;
        for ($h = 0; $h < $n - 1; $h++) {
            $flag = 0;//是否有大小相反的
            for ($i = 0; $i < $n - $h - 1; $i++) {
                $this->times++;
                if ($arr[$i] > $arr[$i + 1]) {
                    $flag = 1;
                    //使用list来将数组中的值赋给一组变量: 交换数组的两个值
                    list($arr[$i], $arr[$i + 1]) = [$arr[$i + 1], $arr[$i]];
                }
            }
            if ($flag == 0) {
                return $arr;
            }
        }
        return $arr;
    }

    //冒泡排序2
    function sort_bubble2($arr) {
        $n = count($arr);
        if ($n <= 1) {
            return $arr;
        }
        $this->times = 0;
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {//与sort_bubble相比, 只是第二次循环时变量直接设定为 $j = $i+1 了
                $this->times++;
                if ($arr[$i] > $arr[$j]) {
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                }
            }
        }
        return $arr;
    }

    //快速排序
    public function quickSort($arr) {
        $n = count($arr);
        if ($n <= 1) {
            return $arr;
        }

        //选择一个基准数
        $baseNum = $arr[0];

        $arrLeft = [];
        $arrRight = [];
        for ($i = 1; $i < $n; $i++) {//注意循环的起始位置
            $this->times++;
            if ($arr[$i] < $baseNum) {
                $arrLeft[] = $arr[$i];
            }
            else {
                $arrRight[] = $arr[$i];
            }
        }
        $arrLeft = $this->quickSort($arrLeft);
        $arrRight = $this->quickSort($arrRight);
        return array_merge($arrLeft, [$baseNum], $arrRight);
    }

    public function resetTimes() {
        $this->times = 0;
    }

    public function getTimes() {
        return $this->times;
    }

}

$m = new SortTest();
$arr = [5, 1, 3, 6, 4, 2];
$arr = [5, 1, 2, 3, 4, 6];
$arr = range(2, 22);
shuffle($arr);
echo implode(',', $arr) . PHP_EOL;
$m->resetTimes();
echo implode(', ', $m->sort_bubble($arr)) . ', ' . '执行' . $m->getTimes() . '次' . PHP_EOL;
$m->resetTimes();
echo implode(', ', $m->sort_bubble2($arr)) . ', ' . '执行' . $m->getTimes() . '次' . PHP_EOL;
$m->resetTimes();
echo implode(', ', $m->quickSort($arr)) . ', ' . '执行' . $m->getTimes() . '次' . PHP_EOL;